
#include <stdlib.h>
#include <stdint.h>
#include "config.h"

#include "zbd-cache.h"
#include "log.h"

#include "algorithms-general.h"

#define SMRC_OBS_WINDOW 100000 
#define SMRC_EXPANSION 2
#define SMRC_THRESHOLD_RATIO 0.2


/* zbd-cache.h */
struct cache_page;
extern struct zbd_zone *zones_collection;
extern struct cache_runtime cache_rt;

extern int RMW(uint32_t zoneId, uint64_t from_blk, uint64_t to_blk); 
extern int Page_force_drop(struct cache_page *page);


/* smrc_ieeeaccess-specified objs */
struct page_payload{
    uint64_t stamp;
    struct cache_page *lru_w_pre, *lru_w_next;
    struct cache_page *lru_r_pre, *lru_r_next;
    int status;
};

static uint64_t Stamp_GLOBAL = 0;
static uint64_t Stamp_OOD = 0; // = Stamp_GLOBAL - window;
static uint64_t Stamp_last_OOD  = 0;
static int smrc_obs_conuter = 0;


// CARS对读/写数据分来管理：写数据按zone组织lru，读数据按全局组织lru
struct smrc_ieeeaccess_lru {
    struct cache_page *head, *tail;
    int score;
};  // 该结构体用于 (struct zbd_zone *) zone 的 priv字段来表示写block的LRU链表；和用于全局读block的LRU链表。

static struct smrc_ieeeaccess_lru LRU_READ_GLOBAL = {NULL, NULL, 0}; // 全局读block的LRU链表



/* lru Utils */
static inline void lru_insert(struct cache_page *page, int op);
static inline void lru_remove(struct cache_page *page, int op);
static inline void lru_move(struct cache_page *page, int op);
static inline void lru_top(struct cache_page *page, int op);

/* cache out */
static int smrc_ieeeaccess_get_zone_out(int *zoneId, uint32_t *zblk_from, uint32_t *zblk_to, uint32_t *zblks_ars);

int smrc_ieeeaccess_init()
{
    /* init page priv field. */
    struct cache_page *page = cache_rt.pages;
    for (uint64_t i = 0; i < STT.n_cache_pages; page++, i++)
    {
        page->priv = calloc(1, sizeof(struct page_payload));
        if(!page->priv)
            return -1;
    }

    struct zbd_zone *z = zones_collection;
    for(int i = 0; i < N_ZONES; i++, z++){
        z->priv = calloc(1, sizeof(struct smrc_ieeeaccess_lru));
    }

    //SMRC_OBS_WINDOW = STT.n_cache_pages * 100 / 256;
    return 0;
}


int smrc_ieeeaccess_login(struct cache_page *page, int op)
{   
    if(op == FOR_READ){
        log_err_sac("[%s] error: SMRC cache algorithm in our implementation does not support to cache READ blocks. \n", __func__ );
        exit(EXIT_FAILURE);
    }

    lru_insert(page, op);

    struct page_payload *payload = (struct page_payload *)page->priv;

    payload->stamp = Stamp_GLOBAL;
    Stamp_GLOBAL ++;
    return 0;
}

int smrc_ieeeaccess_logout(struct cache_page *page, int op)
{   
    if(op == FOR_READ){
        log_err_sac("[%s] error: SMRC cache algorithm in our implementation does not support to cache READ blocks. \n", __func__ );
        exit(EXIT_FAILURE);
    }

    lru_remove(page, op);
    
    return 0;
}

int smrc_ieeeaccess_hit(struct cache_page *page, int op)
{

    if(op == FOR_READ){
        log_err_sac("[%s] error: SMRC cache algorithm in our implementation does not support to cache READ blocks. \n", __func__ );
        exit(EXIT_FAILURE);
    }

    struct page_payload *payload = (struct page_payload *)page->priv;

    lru_top(page, op);

    if (page->status & (~op)){
        lru_top(page, page->status & (~op)); 
    }
    

    payload->stamp = Stamp_GLOBAL;

    Stamp_GLOBAL ++; 
    return 0;
}

int smrc_ieeeaccess_writeback_privi(int type)
{
    int ret, cnt = 0;
    struct cache_page *page;
    struct cache_page *next_page = NULL;
    struct page_payload *payload;

    int zoneId;
    uint32_t zblk_from, zblk_to, zblks_ars;

    if(type == FOR_READ){
        log_err_sac("[%s] error: SMRC cache algorithm in our implementation does not support to cache READ blocks. \n", __func__ );
        exit(EXIT_FAILURE);
    }



    ret = smrc_ieeeaccess_get_zone_out(&zoneId, &zblk_from, &zblk_to, &zblks_ars);
    if(ret < 0){
        log_err_sac("function error: smrc_ieeeaccess_get_zone_out(). \n" );
        exit(EXIT_FAILURE);
    }
    
EVICT_ZONE:
    ret = RMW(zoneId, zblk_from, zblk_to);
    
    // output write amplification.
    uint32_t rmw_scope = N_ZONEBLK - zblk_from;
    double wa = (double)rmw_scope / zblks_ars;
    log_info_sac("[%s] WA: %.2f (%u/%u)\n", __func__, wa, rmw_scope, zblks_ars);

    return ret;
}

static int smrc_ieeeaccess_get_zone_out(int *zoneId, uint32_t *zblk_from, uint32_t *zblk_to, uint32_t *zblks_ars)
{
    int best_zoneId = -1;
    uint32_t from = 0, to = N_ZONEBLK - 1;
    int best_score = 0;   // arsc = 1 / smrc_ieeeaccess = ood_blks / rmw_length .   {0< arsc <= 1}
    int best_zone_hits = 0;
    int rescore = 0;

    if(Stamp_GLOBAL < SMRC_OBS_WINDOW)
        return -1;
        
    if(smrc_obs_conuter <= 0){     
        rescore = 1;
        smrc_obs_conuter = SMRC_OBS_WINDOW; // 重置倒计时器
        Stamp_OOD = Stamp_last_OOD; 
        Stamp_last_OOD = Stamp_GLOBAL;
    }

    // Traverse every zone. 
    struct zbd_zone *z = zones_collection;
    for(int i = 0; i < N_ZONES; i++, z++)
    {
        struct smrc_ieeeaccess_lru * zone_lru = (struct smrc_ieeeaccess_lru *)z->priv;
        if(zone_lru->head == NULL) { continue; }

        uint32_t blkoff_min = 0;
        int myscore = z->cblks;

        // Traverse every page in zone. 
        int hits_in_window = 0;
        
        if(rescore){         
            struct cache_page *page = zone_lru->tail;
            struct page_payload *payload;   
            int threshold = z->cblks * SMRC_THRESHOLD_RATIO;
            while(page)
            {
                payload = (struct page_payload *)page->priv;
                if(payload->stamp >= Stamp_OOD){
                    hits_in_window ++;
                }

                page = payload->lru_w_pre;
            }

            if(zone_lru->score < (int)z->cblks){
                zone_lru->score = z->cblks;
            } 

            if(hits_in_window >= threshold && zone_lru->score > (int)z->cblks) {
                zone_lru->score = zone_lru->score / SMRC_EXPANSION;
            }

            if(hits_in_window < threshold) {
                zone_lru->score = zone_lru->score * SMRC_EXPANSION;
            }

            if(zone_lru->score < 0){
                zone_lru->score = ~(1 << 31);
            }

            myscore = zone_lru->score;
        }

        if(myscore > best_score){
            best_score = myscore;
            best_zoneId = z->zoneId;
            best_zone_hits = hits_in_window;
        }
    }
    z = zones_collection + best_zoneId;
    struct smrc_ieeeaccess_lru * z_priv = (struct smrc_ieeeaccess_lru *)z->priv;
    z_priv->score = 0;

    log_info_sac("[%s] zoneId: %d, cacheblocks: %d, hits: %d, Pe: %d\n", __func__, best_zoneId, z->cblks, best_zone_hits, best_score);

    smrc_obs_conuter -= z->cblks;

    *zoneId = best_zoneId;
    *zblk_from = from;
    *zblk_to = to;
    *zblks_ars = z->cblks;

    return best_zoneId;
}





/* lru Utils */
static inline void lru_insert(struct cache_page *page, int op)
{
    struct zbd_zone *zone = zones_collection + page->belong_zoneId;

    struct smrc_ieeeaccess_lru * zone_lru = (struct smrc_ieeeaccess_lru *)zone->priv;
    struct page_payload *payload = (struct page_payload *)page->priv;

    #ifdef DEBUG_CARS // 用于调试zbd-cache.c代码的正确性
    if(payload->status & op)
    {
        // already in lru link
        log_err_sac("[error] func:%s, page is already in LRU list. \
            You may call algorithm.logout() before algorithm.login() \n");
        exit(-1);
    }
    #endif

    if (op & FOR_WRITE){

        if (zone_lru->head == NULL)
        {
            zone_lru->head = zone_lru->tail = page;
        }
        else
        {
            struct page_payload *header_payload = (struct page_payload *)zone_lru->head->priv;

            payload->lru_w_pre = NULL;
            payload->lru_w_next = zone_lru->head;
            
            header_payload->lru_w_pre = page;
            zone_lru->head = page;
        }  
    } 
    
    if (op & FOR_READ) {

        if (LRU_READ_GLOBAL.head == NULL)
        {
            LRU_READ_GLOBAL.head = page;
            LRU_READ_GLOBAL.tail = page;
        }
        else
        {
            struct page_payload *header_payload = (struct page_payload *)LRU_READ_GLOBAL.head->priv;

            payload->lru_r_pre = NULL;
            payload->lru_r_next = LRU_READ_GLOBAL.head;

            header_payload->lru_r_pre = page;
            LRU_READ_GLOBAL.head = page;
        }       
    }

    payload->status |= op;
}

static inline void lru_remove(struct cache_page *page, int op)
{
    struct page_payload *payload_this = (struct page_payload *)page->priv;
    struct page_payload *payload_pre, *payload_next;

    if ((op & FOR_WRITE) && (payload_this->status & FOR_WRITE)) {

        struct zbd_zone *zone = zones_collection + page->belong_zoneId;
        struct smrc_ieeeaccess_lru * zone_lru = (struct smrc_ieeeaccess_lru *)zone->priv;    

        if(payload_this->lru_w_pre)
        {
             payload_pre = (struct page_payload *)payload_this->lru_w_pre->priv;
             payload_pre->lru_w_next = payload_this->lru_w_next;
        } else 
        {
            zone_lru->head = payload_this->lru_w_next;
        }
        
        if(payload_this->lru_w_next){
             payload_next = (struct page_payload *)payload_this->lru_w_next->priv;
             payload_next->lru_w_pre = payload_this->lru_w_pre;
        } else 
        {
            zone_lru->tail = payload_this->lru_w_pre;
        }
        payload_this->lru_w_pre = payload_this->lru_w_next = NULL;

    }
    
    if ((op & FOR_READ) && (payload_this->status & FOR_READ)) {
        if(payload_this->lru_r_pre)
        {
             payload_pre = (struct page_payload *)payload_this->lru_r_pre->priv;
             payload_pre->lru_r_next = payload_this->lru_r_next;
        } else 
        {
            LRU_READ_GLOBAL.head = payload_this->lru_r_next;
        }
        
        if(payload_this->lru_r_next)
        {
             payload_next = (struct page_payload *)payload_this->lru_r_next->priv;
             payload_next->lru_r_pre = payload_this->lru_r_pre;
        } else 
        {
            LRU_READ_GLOBAL.tail = payload_this->lru_r_pre;
        }
        
        payload_this->lru_r_pre = payload_this->lru_r_next = NULL;
    }

    payload_this->status &= (~op);
}

static inline void lru_top(struct cache_page *page, int op)
{
    lru_remove(page, op);
    lru_insert(page, op);
}

